#Author: Yuan Li
#Title: 15110-lab4
#Date: August 1st 2011


# Global:
helperForest = None
sizeCnt = None
###################

def makeBlankList(height, width, element):
    #do not use this function if element is list-type
    l = []
    row = [element] * width
    for r in xrange(height): l.append(row + [])
    return l

def fireStarter(forest, row, col):
	global helperForest, sizeCnt

	# clean up the dirty in forest
	for rowTuple in forest:
		for item in rowTuple:
			if item == "fire" or item == "no fire":
				continue
			else:
				item = "no fire"
	
	# get the dimension of the forest
	rowF = len(forest)
	colF = len(forest[0])

	# Global variable for fireSize
	# create helperForest
	helperForest = makeBlankList(rowF, colF, 0)
	
	# record the fire patch size
	sizeCnt = 0

	fireSize(forest, row, col)
	
	return sizeCnt

def fireSize(forest, row, col):
	global helperForest, sizeCnt

	# Base case(contains some stop condition and action:
	# check the boundary
	if row >= len(forest) or row < 0:
		return 0
	if col >= len(forest[0]) or col < 0:
		return 0

	# check the hit history
	if helperForest[row][col] == 1:
		return 1

	# check the fire and update the sizeCnt and helperForest
	helperForest[row][col] = 1

	if forest[row][col] == "fire":
		sizeCnt += 1
	# we only check the surround of the fire spot, so skip no fire spot
	else:
		return 1

	#############################################

	# Recursive case

	"""
	searching scope:
	(i-1,j-1) (i-1,j)  (i-1,j+1)
	(i,j-1)    (i,j)    (i,j+1)
	(i+1,j-1) (i+1,j)  (i+1,j+1)

	"""
	fireSize(forest, row-1, col-1)
	fireSize(forest, row-1, col)
	fireSize(forest, row-1, col+1)
	fireSize(forest, row, col-1)
	fireSize(forest, row, col+1)
	fireSize(forest, row+1, col-1)
	fireSize(forest, row+1, col)
	fireSize(forest, row+1, col+1)
	############################################


# Test code
def testFireStarter():
    print "Testing...",
    X = "fire"
    O = "no fire"
    forest0 =[
        [O,O],
        [O,O]
        ]
    assert(fireStarter(forest0, 0, 0) == 0)
    forest1 = [
        [O,O,O],
        [O,X,O],
        [O,O,O]
        ]
    print fireStarter(forest1, 1, 1)
    assert(fireStarter(forest1, 1, 1) == 1)
    forest2 = [
        [O,X,O],
        [O,X,O],
        [O,O,X]
        ]
    assert(fireStarter(forest2, 2, 2) == 3)
    forest3 = [
        [O,X,O,O,O],
        [O,X,O,X,O],
        [X,O,O,X,O],
        [X,O,X,O,X],
        [X,O,X,X,O],
        [O,O,X,X,O],
        [O,O,O,O,O]
        ]
    assert(fireStarter(forest3, 3, 4) == 8)
    print "all tests passed!"
    print "(but you should still add some more of your own)"







# Driver:

testFireStarter()
